package lc;
import java.util.*;
import org.junit.*;
public class Ex16 {
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            int n = nums.length, lo, hi, res = 0, max = Integer.MAX_VALUE;
            // if (n == 3) {
            //     return nums[0] + nums[1] + nums[2];
            // }
            Arrays.sort(nums);
            for (int i = 0; i < n - 2; i++) {
                lo = i + 1;
                hi = n - 1;
                while (lo < hi) {
                    int sum = nums[lo] + nums[hi] + nums[i];
                    int tar = target - sum;
                    // if (sum == 3) {
                    //     System.out.println(Arrays.toString(nums));
                    //     System.out.println(i + "_" + lo + "_" + hi);
                    // }

                    if (tar == 0) {
                        return sum;
                    } else if (tar < 0) {
                        hi--;
                    } else {
                        lo++;
                    }

                    tar = Math.abs(tar);
                    if (tar < max) {
                        max = tar;
                        res = sum;
                    }
    
                }
            }
            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{0,1,2};
        System.out.println(s.threeSumClosest(nums, 3));
    }
    
}
